package com.zang.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合总和III
 * @author ZVerify
 * @since 2022/11/11 20:16
 * @see <a href="https://leetcode.cn/problems/combination-sum-iii/">...</a>
 **/
public class 组合总和III {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int sum = 0;
    public List<List<Integer>> combinationSum3(int k, int n) {

        backtrack(n,k,1);

        return result;
    }

    private void backtrack(int n, int k, int startIndex) {

        // 等于的时候并且里边有k个数则添加
        if (sum==n && list.size()==k) {
            result.add(new ArrayList<>(list));
        }
        // 1-9
        for (int j = startIndex; j <=9; j++) {
            // 大于的时候直接树枝剪掉
            if (sum+j > n) continue;
            sum+=j;
            list.add(j);
            // 递归进入下一层
            backtrack(n,k,j+1);
            // 回溯
            sum-=j;
            list.remove(list.size()-1);

        }
    }
}
